package algorithm.dynamic_planning.leetcode;

import java.util.Arrays;

/**
 * @author yuisama
 * @date 2022年12月11日 18:33
 * @description LCS问题
 * 对于两个字符串求子序列的问题，大概率都是两个指针i和j分别在两个字符串上移动的dp问题
 */
public class Num1143_LongestCommonSubsequence {
    //    // 1.自顶向下的dp思路
//    int[][] memo;
//    public int longestCommonSubsequence(String text1, String text2) {
//        // 备忘录初始化
//        memo = new int[text1.length()][text2.length()];
//        for (int[] row : memo) {
//            Arrays.fill(row,-1);
//        }
//        return dp(text1,0,text2,0);
//    }
//
//    /**
//     * 在s1[i..n) 和s2[j..n) 上寻找lcs，返回lcs的最大长度
//     * @param s1 字符串1
//     * @param i
//     * @param s2 字符串2
//     * @param j
//     * @return
//     */
//    private int dp(String s1, int i, String s2, int j) {
//        // 1.base case
//        if (i == s1.length() || j == s2.length()) {
//            // 一个字符串已经为空,此时一定不存在lcs
//            return 0;
//        }
//        // 2.查备忘录
//        if (memo[i][j] != -1) {
//            // 备忘录中已经存储当前解
//            return memo[i][j];
//        }
//        if (s1.charAt(i) == s2.charAt(j)) {
//            // 当前字符一定算在lcs中
//            memo[i][j] = 1 + dp(s1,i++,s2,j++);
//        }else {
//            // 当前要么s1的字符不在lcs中，要么s2的字符不在lcs中，取最大值
//            memo[i][j] = Math.max(dp(s1,i++,s2,j),
//                    dp(s1,i,s2,j++));
//        }
//        return memo[i][j];
//    }
    // 2.自底向上的dp数组
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
        // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 数组索引和字符串长度差了一个单位偏移量，因此此处为i-1和j-1
                // i和j都从1开始计数
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
